#include <algorithm>
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::max;
using std::pair;
using std::vector;
#define ep emplace_back
#define lld long long
#define mod %

// 取模加法 (a + b) % MOD_N
lld mod_add(lld a, lld b, lld MOD_N) {
  return (a mod MOD_N + b mod MOD_N) mod MOD_N;
}

// 取模乘法 (a * b) % MOD_N
lld mod_mul(lld a, lld b, lld MOD_N) {
  return (a mod MOD_N * b mod MOD_N) mod MOD_N;
}
void solve() {
  lld a, c, m, n;
  cin >> a >> c >> m >> n;
  vector<lld> X(m);
  X[0] = 0;
  for (int i = 1; i < m; ++i) {
    X[i] = (a * X[i - 1] + c) % m;
    // X[i] = mod_add(mod_mul(a, X[i - 1], m), c, m);
  }

  vector<pair<lld, int>> events;
  for (lld x : X) {
    events.ep(x + 1, 1);
    events.ep(x + n + 1, -1);
  }

  sort(events.begin(), events.end(), [](pair<lld, int> a, pair<lld, int> b) {
    if (a.first == b.first) {
      return a.second < b.second; // -1排在+1前面
    }
    return a.first < b.first;
  });

  int curr = 0, ans = 0;
  for (auto x : events) {
    curr += x.second;
    ans = max(ans, curr);
  }
  cout << ans << '\n';
}

int main() {
  int T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}